package _220313;

/**
 * @author ShadowLim
 * @create 2022-03-13-10:27
 */


/** 二维dp（01背包问题）
 * dp[i][j] : 前i个质数可以组成和为j的方案数  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - prime[i]]
 * 转为一维dp --> dp[j] = dp[j] + dp[j - prime[i]] 即 dp[j] += dp[j - prime[i]]
 */
public class _质数拆分 {
    static int cnt = 0, idx = 0;
    static int[] prime = new int[2019];
    static long[] f = new long[2021];   // 一维dp: f[n]表示两个质数之和为n的方案数

    public static void main(String[] args) {
        for (int i = 1; i <= 2019; i++) {
            if (isPrime(i)) {
                prime[idx] = i;
                idx++;
            }
        }
        f[0] = 1;
        for (int i = 0; i < idx; i++) {
            for (int j = 2019; j >= prime[i]; j--) {
                f[j] += f[j - prime[i]];
            }
        }
        System.out.println(f[2019]);
    }

    private static boolean isPrime(int n) {
        if (n == 1) {
            return false;
        }
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}
